package array;

public class QuickSort {
	public static void qsort1(int[] array, int l, int u){
		if(l >=u)
			return;
		
		int pivot = array[l];
		
		int m = l;
		for(int i = l + 1; i <= u; i++){
			if(array[i] < pivot){
				++m;
				int tmp = array[m];
				array[m] = array[i];
				array[i] = tmp;
			}
		}
		
		array[l] = array[m];
		array[m] = pivot;
		
		qsort1(array,l,m-1);
		qsort1(array,m+1,u);
	}

	public static void qsort3(char[] array, int l, int u){
		if(l >= u)
			return;
		char pivot = array[l];
		
		int i = l;
		int j = u +1;
		
		while(true){
			do{
				i++;
			}while(i <= u && array[i] < pivot);
			do{
				j--;
			}while(j > l && array[j] > pivot);
			if(i > j)
				break;
			char tmp = array[i];
			array[i] = array[j];
			array[j] = tmp;
		}
		array[l] = array[j];
		array[j] = pivot;
		
		qsort3(array,l,j-1);
		qsort3(array,j+1,u);
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
